package com.wuyou.simple;

/**
 * 35. 搜索插入位置
 */
public class SearchInsert {


    public static void main(String[] args) {
        int[] nums = {1,3,5,6};
        int target = 2;


        System.out.println(sol_1(nums, target));
    }

    public static int sol_1(int[] nums, int target){
        int l = 0, r = nums.length - 1, mid = nums.length / 2, targetIndex = 0;
        while (l <= r) {
            if (nums[mid] == target) {
                targetIndex = mid;
                break;
            }
            if(nums[l] <= target && target < nums[mid]){
                r = mid - 1;
                mid = ((r - l) / 2) + l;
            }else if(nums[mid] < target && target <= nums[r]){
                l = mid + 1;
                mid = ((r - l) / 2) + l;
            }else {
                if (nums[l] > target) {
                    targetIndex = l;
                    break;
                }
                if (nums[r] < target) {
                    targetIndex = r + 1;
                    break;
                }
            }
        }
        return targetIndex;
    }
}
